package com.sheng.leetcode.year2022.month12.day14;

import org.junit.Test;

import java.util.Arrays;

/**
 * @author liusheng
 * @date 2022/12/14
 * <p>
 * 1697. 检查边长度限制的路径是否存在<p>
 * <p>
 * 给你一个 n 个点组成的无向图边集 edgeList ，<p>
 * 其中 edgeList[i] = [ui, vi, disi] 表示点 ui 和点 vi 之间有一条长度为 disi 的边。<p>
 * 请注意，两个点之间可能有 超过一条边 。<p>
 * 给你一个查询数组queries ，其中 queries[j] = [pj, qj, limitj] ，<p>
 * 你的任务是对于每个查询 queries[j] ，<p>
 * 判断是否存在从 pj 到 qj 的路径，且这条路径上的每一条边都 严格小于 limitj 。<p>
 * 请你返回一个 布尔数组 answer ，其中 answer.length == queries.length ，<p>
 * 当 queries[j] 的查询结果为 true 时， answer 第 j 个值为 true ，否则为 false 。<p>
 * <p>
 * 示例 1：<p>
 * 输入：n = 3, edgeList = [[0,1,2],[1,2,4],[2,0,8],[1,0,16]], queries = [[0,1,2],[0,2,5]]<p>
 * 输出：[false,true]<p>
 * 解释：上图为给定的输入数据。注意到 0 和 1 之间有两条重边，分别为 2 和 16 。<p>
 * 对于第一个查询，0 和 1 之间没有小于 2 的边，所以我们返回 false 。<p>
 * 对于第二个查询，有一条路径（0 -> 1 -> 2）两条边都小于 5 ，所以这个查询我们返回 true 。<p>
 * <p>
 * 示例 2：<p>
 * 输入：n = 5, edgeList = [[0,1,10],[1,2,5],[2,3,9],[3,4,13]], queries = [[0,4,14],[1,4,13]]<p>
 * 输出：[true,false]<p>
 * 解释：上图为给定数据。<p>
 * <p>
 * 提示：<p>
 * 2 <= n <= 10^5<p>
 * 1 <= edgeList.length, queries.length <= 10^5<p>
 * edgeList[i].length == 3<p>
 * queries[j].length == 3<p>
 * 0 <= ui, vi, pj, qj <= n - 1<p>
 * ui != vi<p>
 * pj != qj<p>
 * 1 <= disi, limitj <= 10^9<p>
 * 两个点之间可能有 多条 边。<p>
 * <p>
 * 来源：力扣（LeetCode）<p>
 * 链接：<a href="https://leetcode.cn/problems/checking-existence-of-edge-length-limited-paths">1697. 检查边长度限制的路径是否存在</a><p>
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。<p>
 */
public class LeetCode1697 {

    @Test
    public void test01() {
//        int n = 3;
//        int[][] edgeList = {{0, 1, 2}, {1, 2, 4}, {2, 0, 8}, {1, 0, 16}}, queries = {{0, 1, 2}, {0, 2, 5}};
//        int n = 5;
//        int[][] edgeList = {{0, 1, 10}, {1, 2, 5}, {2, 3, 9}, {3, 4, 13}}, queries = {{0, 4, 14}, {1, 4, 13}};
//        int n = 13;
//        int[][] edgeList = {
//                {9, 1, 53}, {3, 2, 66}, {12, 5, 99}, {9, 7, 26}, {1, 4, 78}, {11, 1, 62}, {3, 10, 50}, {12, 1, 71},
//                {12, 6, 63}, {1, 10, 63}, {9, 10, 88}, {9, 11, 59}, {1, 4, 37}, {4, 2, 63}, {0, 2, 26}, {6, 12, 98},
//                {9, 11, 99}, {4, 5, 40}, {2, 8, 25}, {4, 2, 35}, {8, 10, 9}, {11, 9, 25}, {10, 11, 11}, {7, 6, 89},
//                {2, 4, 99}, {10, 4, 63}},
//                queries = {
//                {9, 7, 65}, {9, 6, 1}, {4, 5, 34}, {10, 8, 43}, {3, 7, 76}, {4, 2, 15}, {7, 6, 52}, {2, 0, 50},
//                {7, 6, 62}, {1, 0, 81}, {4, 5, 35}, {0, 11, 86}, {12, 5, 50}, {11, 2, 2}, {9, 5, 6}, {12, 0, 95},
//                {10, 6, 9}, {9, 4, 73}, {6, 10, 48}, {12, 0, 91}, {9, 10, 58}, {9, 8, 73}, {2, 3, 44}, {7, 11, 83},
//                {5, 3, 14}, {6, 2, 33}};
        int n = 13;
        int[][] edgeList = {
                {9, 14, 88}, {11, 27, 51}, {29, 22, 58}, {29, 27, 26}, {18, 20, 97}, {25, 4, 12}, {2, 4, 16}, {17, 18, 40}, {21, 9, 37},
                {3, 14, 6}, {8, 23, 24}, {7, 27, 39}, {24, 16, 95}, {9, 29, 19}, {9, 18, 22}, {26, 21, 12}, {12, 14, 81}, {6, 14, 79},
                {3, 16, 47}, {13, 19, 18}, {24, 15, 59}, {14, 20, 26}, {24, 20, 14}, {25, 26, 7}, {13, 12, 81}, {1, 0, 51}, {17, 4, 39},
                {8, 16, 77}, {28, 9, 53}, {23, 6, 40}, {29, 18, 31}, {10, 9, 35}, {29, 27, 7}, {1, 29, 91}, {10, 19, 70}, {28, 29, 58},
                {20, 17, 86}, {21, 14, 77}, {19, 4, 43}, {26, 21, 22}, {2, 26, 61}, {24, 22, 16}},
                queries = {{15, 11, 64}, {11, 20, 62}};
        System.out.println(Arrays.toString(new Solution().distanceLimitedPathsExist(n, edgeList, queries)));
    }
}

/**
 * 根据题目要求，我们需要对每个查询 queries[i] 进行判断，即判断当前查询的两个点 a 和 b 之间是否存在一条边权小于等于 limit 的路径。<p>
 * 判断两点是否连通可以通过并查集来实现。另外，由于查询的顺序对结果没有影响，因此我们可以先将所有查询按照 limit 从小到大排序，所有边也按照边权从小到大排序。<p>
 * 然后对于每个查询，我们从边权最小的边开始，将边权严格小于 limit 的所有边加入并查集，接着利用并查集的查询操作判断两点是否连通即可。<p>
 * <p>
 * 作者：lcbin<p>
 * 链接：<a href="https://leetcode.cn/problems/checking-existence-of-edge-length-limited-paths/solution/by-lcbin-uwd2/">...</a><p>
 * 来源：力扣（LeetCode）<p>
 * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。<p>
 */
class Solution {
    private int[] p;

    public boolean[] distanceLimitedPathsExist(int n, int[][] edgeList, int[][] queries) {
        p = new int[n];
        // 赋初始值
        for (int i = 0; i < n; ++i) {
            p[i] = i;
        }
        // 点数据通过边长长度进行排序
        Arrays.sort(edgeList, (a, b) -> a[2] - b[2]);
        int m = queries.length;
        boolean[] ans = new boolean[m];
        Integer[] qid = new Integer[m];
        // 给数组 qie 赋初始值
        for (int i = 0; i < m; ++i) {
            qid[i] = i;
        }
        // 以 qid 数组元素为下标获取 queries 元素，并以数组 queries 的第三个元素长度为排序条件从小到大
        Arrays.sort(qid, (i, j) -> queries[i][2] - queries[j][2]);
        // 初始化 j 为 0
        int j = 0;
        // 循环 qid 数组
        for (int i : qid) {
            // 获取对应 queries 元素的值
            int a = queries[i][0], b = queries[i][1], limit = queries[i][2];
            // 如果 j 小余 edgeList.length 并且满足小余边长最大值时
            while (j < edgeList.length && edgeList[j][2] < limit) {
                int u = edgeList[j][0], v = edgeList[j][1];
                p[find(u)] = find(v);
                ++j;
            }
            ans[i] = find(a) == find(b);
        }
        return ans;
    }

    private int find(int x) {
        if (p[x] != x) {
            p[x] = find(p[x]);
        }
        return p[x];
    }
}

/**
 * dfs + 回溯      超时
 */
//class Solution {
//
//    boolean[] answer;
//
//    public boolean[] distanceLimitedPathsExist(int n, int[][] edgeList, int[][] queries) {
//        /**
//         * edgeList[i] = {x ,y , length} 代表从点 x 到点 y 之间存在一条长度为 length 的路径
//         */
//        answer = new boolean[queries.length];
//        for (int i = 0; i < queries.length; i++) {
//            // query = {x, y, length} 代表，从 x 走到 y 的路程中每条边的最短路径必须比 length 小
//            int x = queries[i][0];
//            int y = queries[i][1];
//            int length = queries[i][2];
//            for (int j = 0; j < edgeList.length; j++) {
//                boolean[] booleans = new boolean[edgeList.length];
//                // 找到一个起点
//                if (x == edgeList[j][0] && edgeList[j][2] < length) {
//                    if (y == edgeList[j][1]) {
//                        answer[i] = true;
//                        break;
//                    }
//                    booleans[j] = true;
//                    dfs(edgeList[j][1], edgeList, y, length, i, booleans);
//                } else if (x == edgeList[j][1] && edgeList[j][2] < length) {
//                    if (y == edgeList[j][0]) {
//                        answer[i] = true;
//                        break;
//                    }
//                    booleans[j] = true;
//                    dfs(edgeList[j][0], edgeList, y, length, i, booleans);
//                }
//            }
//        }
//        return answer;
//    }
//
//    public void dfs(int cur, int[][] edgeList, int y, int max, int z, boolean[] booleans) {
//        for (int i = 0; i < edgeList.length; i++) {
//            if (booleans[i]) {
//                continue;
//            }
//            if (edgeList[i][0] == cur && edgeList[i][2] < max) {
//                if (edgeList[i][1] == y) {
//                    answer[z] = true;
//                    return;
//                }
//                booleans[i] = true;
//                dfs(edgeList[i][1], edgeList, y, max, z, booleans);
//                booleans[i] = false;
//            } else if (edgeList[i][1] == cur && edgeList[i][2] < max) {
//                if (edgeList[i][0] == y) {
//                    answer[z] = true;
//                    return;
//                }
//                booleans[i] = true;
//                dfs(edgeList[i][0], edgeList, y, max, z, booleans);
//                booleans[i] = false;
//            }
//        }
//    }
//}
